﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
//对于一个链表，请设计一个时间复杂度为O(n),
//  额外空间复杂度为O(1)的算法，判断其是否为回文结构。
//
//给定一个链表的头指针A，请返回一个bool值，
//代表其是否为回文结构。保证链表长度小于等于900。


struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));//哨兵结点
        dummy->next = A;
        ListNode* fast = dummy;
        ListNode* slow = dummy;
        while (fast && fast->next)  //获取中间结点
        {
            fast = fast->next->next;
            slow = slow->next;
        }

        ListNode* cur = slow->next; //反转链表
        ListNode* next = cur->next;
        ListNode* pre = slow;
        slow->next = NULL; //防止形成环！！！！！
        while (1)
        {
            cur->next = pre;
            pre = cur;
            if (next == NULL) //注意判断的是next而不是cur->next
                break;
            cur = next;
            next = cur->next;
        }

        ListNode* head = A;
        ListNode* tail = cur;
        while (tail != slow)
        {
            if (head->val != tail->val)
                return false;
            tail = tail->next;
            head = head->next;
        }
        return true;
    }
};

//给你两个单链表的头节点 headA 和 headB ，
// 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
//
//图示两个链表在节点 c1 开始相交：
//
//题目数据 保证 整个链式结构中不存在环。
//intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
//listA - 第一个链表
//listB - 第二个链表
//skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
//skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
//评测系统将根据这些输入创建链式数据结构，
//并将两个头节点 headA 和 headB 传递给你的程序。
//如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

//入：intersectVal = 8, listA = [4, 1, 8, 4, 5],
//  listB = [5, 6, 1, 8, 4, 5], skipA = 2, skipB = 3
//输出：Intersected at '8'
//解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
//从各自的表头开始算起，链表 A 为[4, 1, 8, 4, 5]，链表 B 为[5, 6, 1, 8, 4, 5]。
//在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。


  
  struct ListNode 
  {
      int val;
     struct ListNode *next;
 };
 
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    struct ListNode* curA = headA;
    int k = 0;
    int* ar = (int*)malloc(30000 * sizeof(int));
    while (curA) {
        ar[k++] = curA->val;
        curA->val = -1;
        curA = curA->next;
    }
    struct ListNode* curB = headB;
    while (curB && curB->val != -1) {
        curB = curB->next;
    }
    curA = headA;
    int i = 0;
    while (curA) {
        curA->val = ar[i++];
        curA = curA->next;
    }
    return curB;
}